package com.liyghting.datastructurealgorithm.sort;

/**
 * 归并排序 时间复杂度O(nlogn) 空间复杂度O(n) 稳定，但不是原地排序算法
 * 
 * @author LiYiGuang
 * @date 2018/11/30 14:17
 */
public class MergeSort {
	/**
	 * 归并排序算法
	 * 
	 * @param a
	 *            数组
	 * @param n
	 *            数组大小
	 */
	public static void mergeSort(int[] a, int n) {
		mergeSortInternally(a, 0, n - 1);
	}

	/**
	 * 递归调用，内部归并排序算法
	 * 
	 * @param a
	 *            数组
	 * @param p
	 *            排序开始位置
	 * @param r
	 *            排序结束位置
	 */
	private static void mergeSortInternally(int[] a, int p, int r) {
		if (p >= r)
			return;
		// 取p到r之间的中间位置q,防止（p+r）的和超过int类型最大值
		int q = p + (r - p) / 2;
		// 分治递归
		mergeSortInternally(a, p, q);
		mergeSortInternally(a, q + 1, r);
		// 将A[p...q]和A[q+1...r]合并为A[p...r]
		merge(a, p, q, r);
	}

	/**
	 * 合并
	 * 
	 * @param a
	 * @param p
	 * @param q
	 * @param r
	 */
	private static void merge(int[] a, int p, int q, int r) {
		int i = p;
		int j = q + 1;
		int k = 0;
		int[] temp = new int[r - p + 1];
		while (i <= q && j <= r) {
			if (a[i] <= a[j]) {
				temp[k++] = a[i++];
			} else {
				temp[k++] = a[j++];
			}
		}
		// 判断哪个子数组中有剩余的数据
		int start = i;
		int end = q;
		if (j <= r) {
			start = j;
			end = r;
		}
		while (start <= end) {
			temp[k++] = a[start++];
		}
		// 将tmp中的数组拷贝回a[p...r]
		for (int l = 0; l <= r - p; l++) {
			a[p + l] = temp[l];
		}
	}
	public static void print(int[] a, int n) {
		for (int i = 0; i < n; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}
	public static void main(String[] args) {
		int[] a = {4,5,6,3,2,1};
		mergeSort(a,6);
		print(a,6);
	}
}
